There is a significant and growing market in geographic information systems (GIS) for which multi-attribute indexing is highly important. More generally, multi-attribute indexes are useful whenever the same multiple attributes are used repeatedly in queries, as multi-attribute indexes are more selective and more immediately produce the desired candidate query results. Multi-attribute indexing is significant in connection with GIS where queries are very commonly in terms of coordinates of an area of interest. Although several different conventional systems exist that support multi-attribute indexing via object-relational “blades” or “cartridges”, for example—these are not integrated deeply into database system(s), and in particular, do not exploit concurrency control and recovery features.
An R-tree is a multi-attribute access method of conventional choice. However, it has a number of problems, including overlapping regions, costly index comparisons, low index node fanout (especially as dimensionality increases), and difficulty in tuning.
Another conventional multi-attribute indexing method is the B-tree. Data in relational databases is frequently stored and retrieved using B-trees. The key of the B-tree frequently involves the concatenation of several fields of the relational table to retrieve small subsets to avoid large scans of potentially huge tables.
A Pi-tree is a multi-attribute indexing method that provides a high concurrency index tree that also supports recovery. The Pi-tree is well-documented in the art.
Currently, the manner in which many database systems optimize multi-attribute queries is to exploit one or more single attribute indexes, occasionally they use concatenated key indexes. However, these conventional approaches require examining substantially more data, typically performing an intersection of results from multiple index searches. There has been on-going work in multi-attribute indexes to improve this situation.